import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class 买礼物 {
    //https://www.luogu.com.cn/problem/P1194
    public static int MAXN = 5001;
    public static int[] farther = new int[MAXN];
    //使用动态数组, 使用静态的存不了会报错, 其他思路都没问题
    public static List<int[]> edges = new ArrayList<>();

    public static int n;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int prize = in.nextInt();
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int cur = in.nextInt();
                if(cur != 0 && cur < prize){
                    edges.add(new int[]{i,j,cur});
                }
            }
        }
        build();
        edges.sort((x,y) -> x[2] - y[2]);
        int edgeCnt = 0;
        int ans = 0;
        for(int[] edge : edges){
            if(union(edge[0],edge[1])){
                ans += edge[2];
                edgeCnt++;
            }
        }
        for (int i = 0; i < edges.size(); i++) {

        }
        ans += (n - edgeCnt) * prize;
        System.out.println(ans);
    }

    private static void build() {
        for (int i = 1; i <= n; i++) {
            farther[i] = i;
        }
    }
    private static int find(int i){
        if(farther[i] != i){
            farther[i] = find(farther[i]);
        }
        return farther[i];
    }

    private static boolean union(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            farther[fx] = fy;
            return true;
        }else {
            return false;
        }
    }
}
